#include "uthreads.h"
#include "translateAddress.h"
#include "thread.h"
#include "queue.h"
#include <stdlib.h>
#include <sys/time.h>
#include <limits.h>
#include <setjmp.h>
#include <signal.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>

//Internal Interface
typedef unsigned long address_t; //64bit address
#define JB_SP 6
#define JB_PC 7

//Error messages:
const char* SYSTEM_ERROR_MSG = "system error: ";
const char* LIBRARY_ERROR_MSG = "thread library error:";
const char* LIB_INIT_ERROR_MSG = "Library initialization failed.\n";
const char* SPAWN_ERROR_MSG = "Thread spawn failed.\n";
const char* SUSPEND_ERROR_MSG = "Thread suspension failed.\n";
const char* RESUME_ERROR_MSG = "Thread resume failed.\n";
const char* SET_PRIORITY_ERROR_MSG = "Thread set priority failed.\n";
const char* SLEEP_ERROR_MSG = "Thread sleep failed.\n";
const char* TERMINATE_ERROR_MSG = "Thread termination failed.\n";

//program constants:
#define FAIL -1
#define SUCCESS 0
#define MAIN_THREAD_PRIORITY MAX_PRI/2

//---------------------------Global Variables---------------------------------
//Containing pointers to all existing thread, thread with id k is in the kth cell:
Thread** threads_id_arr;
int threads_arr_size;

//An array of ready queues, a queue for each priority:
Queue* ready_threads[MAX_PRI+1];

//this struct holds the ids of threads according to their time stamp and helps to manage time stamps.
//the tid of the thread whose time stamp is 2 is in the second array cell.
typedef struct thread_time_stamp{
	unsigned int* _thread_waiting_stamp;
	int _thread_waiting_size;
}Thread_time_stamp;

//an instance of the thread_time_stamp, helps to manage thread's time stamps:
Thread_time_stamp ready_threads_time_stamp;

unsigned int running_thread_id;
unsigned int toBeExecutedThreadId = 0;
int sleeping_thread_id;

//---------------------------Private functions-------------------------------
//main logic function of the class, decides and runs the thread that suppose to run:
void makeSchedualeDecision();

//signal handler:
void handleAwakeningThread(int sig);

//prints the given error message to stderr:
void printLibraryError(const char* error);

//Checks the return value of a system call:
int catchSysCallError(int answer);

//Shifts the ready thread's ready stamps.
void shiftUpReadyThreadsStamps(unsigned int index);

//Changes the state of the thread with the given tid into sleeping for
//the given amount of time:
int sendThreadToSleep(unsigned int tid, int millisecs);

//Returns the id of the thread with highest priority and the longest waiting time
//amongst the thread with the highest priority.
unsigned int pickThreadToRun();

//Removes a thread from the ready queue and updates the ready queue accordingly:
void removeFromReadyThreads(int tid);

//Assigns the thread to the thread array according to it's tid:
void assignThreadToThreadArray(Thread* thread);

//Changes the state of the thread to 'ready' and puts the index of the thread into
//the end of the queue according to its priority
int assignThreadToReadyQueue(int tid);

//Releases all Thread and resources allocated by the library
int freeAllThreadsAndResources();

//Finds an available index for the thread and assigns the Thread's address to the id's array
unsigned int getNextThreadID();

//Checks if a id is legal and thread exists
int isThreadIdValid(int tid);

//frees the memory taken up by the thread with the given tid, and updates the
//data structures accordingly:
int freeThread(int tid);

//Blocks the SIGVTALARM signal
int blockAwakeningThreadSig();

//Unblocks the SIGVALARM signal:
int unblockAwakeningThreadSig();

//Finds an available index for the thread and assigns the Thread's address to the id's array
unsigned int getNextThreadID();

//Checks if a id is legal and thread exists
int isThreadIdValid(int tid);

//Checks if a thread priority is legal
int isPriorityValid(int priority);

//Initialized thread's stack:
void initializeThreadStack(Thread* thread, void (*thread_func)(void));

//handles the return of a thread from sleeping state:
void handleAwakeningThread(int sig);

//Prints a library error:
void printLibraryError(const char* errorMSG);

//---------------------------Implementation-------------------------------

//Checks the return value of a system call, if the system call ended with an error,
//the function prints an error method and terminated responsible thread:
int catchSysCallError(int answer) {
	if (answer == -1) {
		fprintf(stderr,"%s",SYSTEM_ERROR_MSG);
		thread_terminate(thread_gettid());
		return FAIL;
	} else {
		return SUCCESS;
	}
}

//Shifts the ready thread's ready stamps.
void shiftUpReadyThreadsStamps(unsigned int index){
	int i;
	for(i = index;i<ready_threads_time_stamp._thread_waiting_size-1;i++){
		threads_id_arr[ready_threads_time_stamp._thread_waiting_stamp[i+1]]->_readyTimeStamp=i;
		ready_threads_time_stamp._thread_waiting_stamp[i] = ready_threads_time_stamp._thread_waiting_stamp[i+1];
	}
}

//Changes the state of the thread with the given tid into sleeping for
//the given amount of time:
int sendThreadToSleep(unsigned int tid, int millisecs) {
	struct sigaction new_action;
	new_action.sa_handler = handleAwakeningThread;
	if (catchSysCallError(sigemptyset(&new_action.sa_mask)) == FAIL) {
		return FAIL;
	}
	new_action.sa_flags = 0;
	if (catchSysCallError(sigaction(SIGVTALRM, &new_action, NULL)) == FAIL) {
		return FAIL;
	}
	struct itimerval tv;
	tv.it_value.tv_sec = millisecs / 1000; //time of first timer
	tv.it_value.tv_usec = (millisecs % 1000) * 1000; //time of first timer
	tv.it_interval.tv_sec = 0; //time of all timers but the first one
	tv.it_interval.tv_usec = 0; //time of all timers but the first one

	sleeping_thread_id = tid;

	if (catchSysCallError(setitimer(ITIMER_VIRTUAL, &tv, NULL)) == FAIL) {
		return FAIL;
	}
	return SUCCESS;
}

//Returns the id of the thread with highest priority and the longest waiting time
//amongst the thread with the highest priority.
//This function assumes there will be a valid id to return
unsigned int pickThreadToRun() {
	int priorityIndex = 0;
	Thread* threadToRun;
	while (priorityIndex <= MAX_PRI) {
		threadToRun = peekThreadPointerFromQueue(ready_threads[priorityIndex]);
		if (threadToRun == NULL) {
			priorityIndex++;
		} else {
			break;
		}
	}
	if (threads_id_arr[running_thread_id] != NULL &&
			priorityIndex >= threads_id_arr[running_thread_id]->_priority &&
			threads_id_arr[running_thread_id]->_currentState == RUNNING) {
		return running_thread_id;
	} else {
		removeThreadFromQueue(ready_threads[priorityIndex],threadToRun);
		return threadToRun->_id;
	}
}

//Removes a thread from the ready list and updates the ready list accordingly
void removeFromReadyThreads(int tid) {
	Queue* queueToRemoveFrom = ready_threads[threads_id_arr[tid]->_priority];
	removeThreadFromQueue(queueToRemoveFrom, threads_id_arr[tid]);
	shiftUpReadyThreadsStamps(threads_id_arr[tid]->_readyTimeStamp);
	ready_threads_time_stamp._thread_waiting_stamp = realloc(ready_threads_time_stamp._thread_waiting_stamp,
			sizeof(unsigned int) * (ready_threads_time_stamp._thread_waiting_size -1));
	ready_threads_time_stamp._thread_waiting_size--;
}

//Assigns the thread to the thread array according to it's tid:
void assignThreadToThreadArray(Thread* thread) {
	threads_id_arr[thread->_id] = thread;
	threads_arr_size++;
}

//Changes the state of the thread to 'ready' and puts the index of the thread into
//the end of the queue according to its priority
int assignThreadToReadyQueue(int tid) {
	threads_id_arr[tid]->_currentState = READY;
	//printf("fot therad: %d , stamp is going to be: %d\n",tid,ready_threads_time_stamp._thread_waiting_size-1);
	threads_id_arr[tid]->_readyTimeStamp = ready_threads_time_stamp._thread_waiting_size-1;
	ready_threads_time_stamp._thread_waiting_stamp[threads_id_arr[tid]->_readyTimeStamp] = tid;
	Queue* queueToAddTo = ready_threads[threads_id_arr[tid]->_priority];
	addThreadToQueue(queueToAddTo, threads_id_arr[tid]);
	ready_threads_time_stamp._thread_waiting_stamp = realloc(ready_threads_time_stamp._thread_waiting_stamp,
			sizeof(unsigned int) * (ready_threads_time_stamp._thread_waiting_size + 1));
	ready_threads_time_stamp._thread_waiting_size++;
	return SUCCESS;
}

//Releases all Thread and resources allocated by the library
int freeAllThreadsAndResources() {
	int i = 0;
	for (i = 0; i < threads_arr_size; i++) {
		if (threads_id_arr[i] != NULL) {
			free(threads_id_arr[i]);
		}
	}
	free(threads_id_arr);
	return SUCCESS;
}

//frees the memory taken up by the thread with the given tid, and updates the
//data structures accordingly:
int freeThread(int tid) {
	if (threads_id_arr[tid]->_currentState == SLEEPING) {
		sleeping_thread_id = -1;
	} else if (threads_id_arr[tid]->_currentState == READY) {
		removeFromReadyThreads(tid);
	}
	free(threads_id_arr[tid]);
	threads_id_arr[tid] = NULL;
	return SUCCESS;
}

//Blocks the SIGVTALARM signal
int blockAwakeningThreadSig() {
	sigset_t set;
	if (catchSysCallError(sigemptyset(&set)) == FAIL
			|| catchSysCallError(sigaddset(&set, SIGVTALRM)) == FAIL
			|| catchSysCallError(sigprocmask(SIG_SETMASK, &set, NULL)) == FAIL) {
		return FAIL;
	}
	return SUCCESS;
}

//Unblocks the SIGVALARM signal:
int unblockAwakeningThreadSig() {
	sigset_t set;
	if (catchSysCallError(sigemptyset(&set)) == FAIL
			|| catchSysCallError(sigprocmask(SIG_SETMASK, &set, NULL)) == FAIL) {
		return FAIL;
	}
	return SUCCESS;
}

//Finds an available index for the thread and assigns the Thread's address to the id's array
unsigned int getNextThreadID() {
	//scan for an available spot
	if(threads_arr_size == 0 || threads_arr_size-1 == INT_MAX){
		return FAIL;
	}
	else{
		threads_id_arr = realloc(threads_id_arr,sizeof(Thread*) * (threads_arr_size + 1));
		if (threads_id_arr == NULL) {
			return FAIL;
		} else {
			return threads_arr_size-1;
		}
	}
}

//Checks if a id is legal and thread exists
int isThreadIdValid(int tid) {
	if (tid < 0 || tid > INT_MAX) {
		return FAIL;
	} else if (threads_id_arr[tid] == 0) {
		return FAIL;
	} else {
		return SUCCESS;
	}
}

//Checks if a thread priority is legal
int isPriorityValid(int priority) {
	if (priority < 0 || priority > MAX_PRI) {
		return FAIL;
	} else {
		return SUCCESS;
	}
}

//Initialized thread's stack:
void initializeThreadStack(Thread* thread, void (*thread_func)(void)) {
	unsigned int sp, pc;
	sp = (address_t) thread->_stack + STACK_SIZE - sizeof(address_t);
	pc = (address_t) thread_func;
	sigsetjmp(thread->_env, 0);
	(thread->_env->__jmpbuf)[JB_SP] = translate_address(sp);
	(thread->_env->__jmpbuf)[JB_PC] = translate_address(pc);
}

//decides which thread should run, and activates it:
void makeSchedualeDecision() {
	toBeExecutedThreadId = pickThreadToRun();
	//if we choose the running thread again there's nothing to jump to
	if (toBeExecutedThreadId == running_thread_id) {
		return;
	} else {
		//if running thread hadn't called terminate on itself we go ahead as planned
		removeFromReadyThreads(toBeExecutedThreadId);
		if (threads_id_arr[running_thread_id] != NULL) {
			if(threads_id_arr[running_thread_id]->_currentState == RUNNING){
				assignThreadToReadyQueue(running_thread_id);
			}
			sigsetjmp(threads_id_arr[running_thread_id]->_env, 0);
		}
		//in case we came back a jump, but when we saved our status originally the 'toBeExecutedThread'
		//was alive and is no longer alive we will not try to jump to it
		if (threads_id_arr[toBeExecutedThreadId] != NULL && toBeExecutedThreadId != running_thread_id) {
			running_thread_id = toBeExecutedThreadId;
			threads_id_arr[running_thread_id]->_currentState = RUNNING;
			siglongjmp(threads_id_arr[toBeExecutedThreadId]->_env, 1);
		}
	}
}

//handles the return of a thread from sleeping state:
void handleAwakeningThread(int sig) {
	assignThreadToReadyQueue(sleeping_thread_id);
	struct timeval tempTime;
	gettimeofday(&tempTime, NULL);
	sleeping_thread_id = -1;
	makeSchedualeDecision();
}

//Prints a library error:
void printLibraryError(const char* errorMSG)
{
	char* result = malloc(strlen(LIBRARY_ERROR_MSG) + strlen(errorMSG) + 2);
	strcpy(result, LIBRARY_ERROR_MSG);
	strcat(result, " ");
	strcat(result, errorMSG);
	fprintf(stderr,"%s",result);
	free(result);
}

/* external interface */

/* Initialize thread library */
int thread_lib_init() {
	int i = 0;
	threads_id_arr = (Thread**) malloc(sizeof(Thread*) * 1);
	if (threads_id_arr == NULL) {
		printLibraryError(LIB_INIT_ERROR_MSG);
		return FAIL;
	}
	threads_arr_size = 1;
	for (i = 0; i <= MAX_PRI; i++) {
		ready_threads[i] = initQueue();
		if (ready_threads[i] == NULL) {
			printLibraryError(LIB_INIT_ERROR_MSG);
			return FAIL;
		}
	}

	ready_threads_time_stamp._thread_waiting_stamp = (unsigned int*) malloc(sizeof(unsigned int) * 1);
	ready_threads_time_stamp._thread_waiting_size = 1;
	if (ready_threads_time_stamp._thread_waiting_stamp == NULL) {
		printLibraryError(LIB_INIT_ERROR_MSG);
		return FAIL;
	}

	running_thread_id = 0;
	sleeping_thread_id = -1;
	//defining the calling thread of this init function as the main thread
	Thread* mainThread = initThread(getNextThreadID(), MAIN_THREAD_PRIORITY);
	assignThreadToThreadArray(mainThread);
	mainThread->_currentState = RUNNING;
	sigsetjmp(mainThread->_env, 0);
	initializeThreadStack(mainThread,(void (*)(void)) (mainThread->_env->__jmpbuf)[JB_PC]);
	return SUCCESS;
}

/* Create a new thread whose entry point is f */
//we're blocking SIGALRT so that a thread that comes back from sleep mode
//will not enter the ready queue before this spawn has finished to keep fairness
int thread_spawn(void (*thread_func)(void), int priority) {
	blockAwakeningThreadSig();
	if (isPriorityValid(priority) == FAIL) {
		printLibraryError(SPAWN_ERROR_MSG);
		return FAIL;
	}
	Thread* newThread = initThread(getNextThreadID(), priority);
	assignThreadToThreadArray(newThread);
	if (newThread == NULL) {
		printLibraryError(SPAWN_ERROR_MSG);
		return FAIL;
	}
	initializeThreadStack(newThread, thread_func);
	if (sigemptyset(&newThread->_env->__saved_mask) == FAIL) {
		printLibraryError(SPAWN_ERROR_MSG);
		return FAIL;
	}
	if (assignThreadToReadyQueue(newThread->_id) == FAIL) {
		printLibraryError(SPAWN_ERROR_MSG);
		return FAIL;
	} else {
		unblockAwakeningThreadSig();
		//This local newID variable is needed in case we are spawning a thread that starts and ends before this function's
		//return statement:
		unsigned int newID = newThread->_id;
		makeSchedualeDecision();
		return newID;
	}
}

int isThreadAlive(unsigned int tid){
	Thread* temp = threads_id_arr[tid];
	if (tid >= threads_arr_size )
	{
		return FAIL;
	}
	else if(temp == NULL)
	{
		return FAIL;
	}
	else
	{
		return SUCCESS;
	}
}

/* Terminate a thread */
int thread_terminate(int tid) {
	blockAwakeningThreadSig();
	if (isThreadIdValid(tid) == FAIL) {
		printLibraryError(TERMINATE_ERROR_MSG);
		unblockAwakeningThreadSig();
		return FAIL;
	}
	else if(isThreadAlive(tid)== FAIL)
	{
		printLibraryError(TERMINATE_ERROR_MSG);
		unblockAwakeningThreadSig();
		return FAIL;
	}
	else if (tid == 0) {
		freeAllThreadsAndResources();
		exit(0);
	} else if (running_thread_id == tid) {
		freeThread(tid);
		makeSchedualeDecision();
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	//Terminating a specific non-running thread
	else {
		int result = freeThread(tid);
		unblockAwakeningThreadSig();
		return result;
	}
}

/* Sleep */
int thread_sleep(int tid, int num_millisecs) {
	blockAwakeningThreadSig();
	//checking if another thread or this specific thread
	if (sleeping_thread_id != -1) {
		printLibraryError(LIB_INIT_ERROR_MSG);
		return FAIL;
	} else if (sleeping_thread_id == tid) {
		printLibraryError(LIB_INIT_ERROR_MSG);
		return FAIL;
	} else if (tid == 0) {
		printLibraryError(LIB_INIT_ERROR_MSG);
		return FAIL;
	}
	switch (threads_id_arr[tid]->_currentState) {
	case SUSPENDED: {
		threads_id_arr[tid]->_currentState = SLEEPING;
		sendThreadToSleep(tid, num_millisecs);
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	case RUNNING: {
		threads_id_arr[tid]->_currentState = SLEEPING;
		sendThreadToSleep(tid, num_millisecs);
		makeSchedualeDecision();
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	case READY: {
		threads_id_arr[tid]->_currentState = SLEEPING;
		removeFromReadyThreads(tid);
		sendThreadToSleep(tid, num_millisecs);
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	//the flow should never reach this line
	default: {
		unblockAwakeningThreadSig();
		return FAIL;
	}
	}
}

/* Suspend */
int thread_suspend(int tid) {
	isThreadIdValid(tid);
	blockAwakeningThreadSig();
	//returning error if trying to suspend the main thread
	if (tid == 0) {
		printLibraryError(SUSPEND_ERROR_MSG);
		unblockAwakeningThreadSig();
		return FAIL;
	}
	switch (threads_id_arr[tid]->_currentState) {
	//Nothing to do here
	case SUSPENDED: {
		break;
	}
	case RUNNING: {
		threads_id_arr[tid]->_currentState = SUSPENDED;
		makeSchedualeDecision();
		break;
	}
	case SLEEPING: {
		threads_id_arr[tid]->_currentState = SUSPENDED;
		sendThreadToSleep(-1, 0);
		break;
	}
	case READY: {
		threads_id_arr[tid]->_currentState = SUSPENDED;
		removeFromReadyThreads(tid);
		break;
	}
	default: {
		return FAIL;
	}
	}
	unblockAwakeningThreadSig();
	return SUCCESS;
}

/* Resume */
int thread_resume(int tid) {
	blockAwakeningThreadSig();
	if(isThreadIdValid(tid)==FAIL)
	{
		printLibraryError(RESUME_ERROR_MSG);
		unblockAwakeningThreadSig();
		return FAIL;
	}

	switch (threads_id_arr[tid]->_currentState) {
	case (SLEEPING): {
		sendThreadToSleep(-1, 0);
		assignThreadToReadyQueue(tid);
		threads_id_arr[tid]->_currentState = READY;
		makeSchedualeDecision();
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	case (SUSPENDED): {
		assignThreadToReadyQueue(tid);
		threads_id_arr[tid]->_currentState = READY;
		makeSchedualeDecision();
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	//if the tid thread is in RUNNING\READY mode, no action is needed:
	default :{
		unblockAwakeningThreadSig();
		return SUCCESS;
	}
	}
	unblockAwakeningThreadSig();
	return FAIL;
}

/* Set Priority */
int thread_set_priority(int tid, int priority) {
	blockAwakeningThreadSig();
	if (isThreadIdValid(tid) == FAIL) {
		printLibraryError(SET_PRIORITY_ERROR_MSG);
		return FAIL;
	}
	if(threads_id_arr[tid]->_currentState == READY){
		removeThreadFromQueue(ready_threads[threads_id_arr[tid]->_priority],threads_id_arr[tid]);
	}
	threads_id_arr[tid]->_priority = priority;
	if(threads_id_arr[tid]->_currentState == READY){
		addThreadToQueue(ready_threads[priority],threads_id_arr[tid]);
	}
	makeSchedualeDecision();
	unblockAwakeningThreadSig();
	return SUCCESS;
}

/* Get thread id */
int thread_gettid() {
	return running_thread_id;
}
